//
//  23. 合并K个升序链表.swift
//  Top600
//
//  Created by rjb on 2021/8/10.
//

import Foundation
class Solution23 {
    // 合并k个有序链表
    // 实际上采用两两合并就可以了
    // 怎么做到两两合并
    // 实际上就是一种分治法
    
    func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        return merge(lists, start: 0, end: lists.count - 1)
    }
    func merge(_ list: [ListNode?], start: Int, end: Int) -> ListNode? {
        if start == end {
            return list[start]
        }
        if start > end {
            return nil
        }
        let mid = (start + end) / 2
        // 左部分合并
        let leftNode = merge(list, start: start, end: mid)
        // 右部分合并
        let rightNode = merge(list, start: mid + 1, end: end)
        // 合并两个链表
        let mergedNode = mergeTowList(one: leftNode, two: rightNode)
        return mergedNode
    }
    func mergeTowList(one: ListNode?, two: ListNode?) -> ListNode? {
        // 合并两个有序链表
        let vHead = ListNode(-1)
        var p: ListNode? = vHead
        var p1 = one
        var p2 = two
        while p1 != nil && p2 != nil {
            if p1!.val < p2!.val {
                p?.next = p1
                p1 = p1?.next
            } else {
                p?.next = p2
                p2 = p2?.next
            }
            p = p?.next
        }
        if p1 == nil {
            p?.next = p2
        }
        if p2 == nil {
            p?.next = p1
        }
        return vHead.next
    }
    static func test(){
        let link1 = [1,4,5]
        let link2 = [1,3,4]
        let link3 = [2,6]
        
        let root1 = createNode(link1)
        let root2 = createNode(link2)
        let root3 = createNode(link3)
        let lists = [root1,root2,root3]
        
        let solution = Solution23()
        let result = solution.mergeKLists(lists)
        print(result)
    }
    static func createNode(_ link: [Int]) -> ListNode?{
        var root: ListNode?
        var p: ListNode?
        for item in link {
            if root == nil {
                root = ListNode(item)
                p = root
            } else {
                p?.next = ListNode(item)
                p = p?.next
            }
        }
        return root
    }
}
